package array;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给你一个由 正 整数组成的数组 nums 。
 * 如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：
 * 子数组中 不同 元素的数目等于整个数组不同元素的数目。
 * 返回数组中 完全子数组 的数目。
 * 子数组 是数组中的一个连续非空序列。
 * <p>
 * 示例 1：
 * 输入：nums = [1,3,1,2,2]
 * 输出：4
 * 解释：完全子数组有：[1,3,1,2]、[1,3,1,2,2]、[3,1,2] 和 [3,1,2,2] 。
 * <p>
 * 示例 2：
 * 输入：nums = [5,5,5,5]
 * 输出：10
 * 解释：数组仅由整数 5 组成，所以任意子数组都满足完全子数组的条件。子数组的总数为 10 。
 *
 * @author Jisheng Huang
 * @version 20250424
 */
public class CountCompleteSubarrInArr_2799 {
    /**
     * Sliding window solution to solve this problem.
     * <p>
     * Input array A has k different values.
     * <p>
     * For each subarray ending at index j,
     * we count the frequency of values in A[i], A[i+1]...A[j]
     * Then we slide the pointer i,
     * to find the minimum index i,
     * that the subarray don't have k different values.
     * which means the subarray starting at 0,1,..,i-1,
     * have k different values.
     * <p>
     * That is i subarray in total,
     * so we update res += i.
     * <p>
     * Finally we return result res.
     *
     * @param nums the given integer array
     * @return the number of complete subarrays
     */
    public static int countCompleteSubarrays(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int a : nums) {
            set.add(a);
        }

        int n = nums.length;
        int k = set.size();
        int res = 0;
        int i = 0;

        Map<Integer, Integer> map = new HashMap<>();

        for (int j = 0; j < n; ++j) {
            if (map.getOrDefault(nums[j], 0) == 0) {
                --k;
            }

            map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);

            while (k == 0) {
                map.put(nums[i], map.get(nums[i]) - 1);

                if (map.get(nums[i]) == 0) {
                    ++k;
                }

                ++i;
            }

            res += i;
        }

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 1, 2, 2};
        System.out.println(countCompleteSubarrays(arr));

        arr = new int[]{5, 5, 5, 5};
        System.out.println(countCompleteSubarrays(arr));
    }
}
